//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 
//
// 
//
// 注意： 
//
// 
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
// 
//
// 示例 2： 
//
// 
//输入：s = "a", t = "a"
//输出："a"
// 
//
// 示例 3: 
//
// 
//输入: s = "a", t = "aa"
//输出: ""
//解释: t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 105 
// s 和 t 由英文字母组成 
// 
//
// 
//进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？ Related Topics 哈希表 字符串 滑动窗口 
// 👍 1467 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * [76]最小覆盖子串
 */
public class MinimumWindowSubstring {
    public static void main(String[] args) {
        Solution solution = new MinimumWindowSubstring().new Solution();
        String result = "";
        result = solution.minWindow("ADOBECODEBANC", "ABC");
        if (!result.equals("BANC")) {
            System.out.println("--1--");
        }

        result = solution.minWindow("a", "a");
        if (!result.equals("a")) {
            System.out.println("--2--");
        }

        result = solution.minWindow("a", "aa");
        if (!result.equals("")) {
            System.out.println("--3--");
        }

    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String minWindow2(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            Integer count = map.getOrDefault(t.charAt(i), 0);
            map.put(t.charAt(i), count+1);
        }

        int left = 0;
        int tempL = 0, tempR = 0;
        int len = s.length() + 1;
        int needConver = map.size();
        for (int i = 0; i < s.length(); i++) {
            Integer count = map.getOrDefault(s.charAt(i), 0);
            map.put(s.charAt(i), count-1);
            if (count == 1) {
                needConver--;
            }

            if (needConver == 0) {
                while (left < i) {
                    count = map.getOrDefault(s.charAt(left), 0);
                    if (count < 0) {
                        map.put(s.charAt(left), count+1);
                        left++;
                        continue;
                    }
                    break;
                }
                if (i - left < len) {
                    len = i - left;
                    tempL = left;
                    tempR = i;
                }
            }
        }

        if (len == s.length() + 1) {
            return "";
        }
        return s.substring(tempL, tempR+1);
    }

    // 用数组代替map进行优化
    public String minWindow(String s, String t) {
        int[] cal = new int['z' - 'A' + 1];
        for (int i = 0; i < t.length(); i++) {
            cal[t.charAt(i) - 'A']++;
        }


        int needConver = 0;
        for (int i = 0; i < cal.length; i++) {
            if (cal[i] != 0) {
                needConver++;
            }
        }

        int left = 0;
        int tempL = 0, tempR = 0;
        int len = s.length() + 1;
        for (int i = 0; i < s.length(); i++) {
            int count = cal[s.charAt(i) - 'A'];
            cal[s.charAt(i) - 'A']--;
            if (count == 1) {
                needConver--;
            }

            if (needConver == 0) {
                while (left < i) {
                    count = cal[s.charAt(left) - 'A'];
                    if (count < 0) {
                        cal[s.charAt(left) - 'A']++;
                        left++;
                        continue;
                    }
                    break;
                }
                if (i - left < len) {
                    len = i - left;
                    tempL = left;
                    tempR = i;
                }
            }
        }

        if (len == s.length() + 1) {
            return "";
        }
        return s.substring(tempL, tempR+1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}